package com.localking.algorithm.leetcode.array.matrix

/**
 * Given a matrix of M * N elements(M rows, N columns), return all elements of the matrix in diagonal order.
 *
 * Example:
 * Input:
 * [
 * [1, 2, 3],
 * [4, 5, 6],
 * [7, 8, 9]
 * ]
 * Output:
 * [1, 2, 4, 7, 5, 3, 6, 8, 9]
 *
 * @author jinbo
 */
object FindDiagonalOrder {
  def main(args: Array[String]): Unit = {
    val matrix = Array(
      Array(1, 2, 3),
      Array(4, 5, 6),
      Array(7, 8, 9)
    )
    println(findDiagonalOrder(matrix).mkString(","))
  }

  def findDiagonalOrder(matrix: Array[Array[Int]]): Array[Int] = {
    var resultArray: Array[Int] = Array.empty
    if (matrix.length > 0) {
      val rows: Int = matrix.length
      val columns: Int = matrix(0).length
      var clockwise: Boolean = true
      for (i <- 0 until rows + columns) {
        val rowMax: Int = if (i <= rows - 1) i else rows - 1
        val columnMax: Int = if (i <= columns - 1) i else columns - 1
        if (clockwise) {
          for (row <- rowMax to 0 by -1) {
            for (column <- 0 to columnMax) {
              if (row + column == i) {
                resultArray :+= matrix(row)(column)
              }
            }
          }
          clockwise = false
        } else {
          for (column <- columns - 1 to 0 by -1) {
            for (row <- 0 to rowMax) {
              if (row + column == i) {
                resultArray :+= matrix(row)(column)
              }
            }
          }
          clockwise = true
        }
      }
    }
    resultArray
  }
}
